import javax.swing.*;

public class OjTest1 {
    public static void main(String[] args) {

    }
}
/*给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。*/
class Solution5 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        int lenA = getLength(headA);
        int lenB = getLength(headB);

        ListNode ptrA = headA;
        ListNode ptrB = headB;

        // 将较长的链表指针先向后移动|lenA - lenB|个位置
        if (lenA > lenB) {
            int diff = lenA - lenB;
            while (diff > 0) {
                ptrA = ptrA.next;
                diff--;
            }
        } else if (lenB > lenA) {
            int diff = lenB - lenA;
            while (diff > 0) {
                ptrB = ptrB.next;
                diff--;
            }
        }

        // 同时移动两个指针，寻找相交节点
        while (ptrA != null && ptrB != null) {
            if (ptrA == ptrB) {
                return ptrA;
            }
            ptrA = ptrA.next;
            ptrB = ptrB.next;
        }

        return null; // 没有相交节点，返回null
    }

    // 辅助函数，获取链表的长度
    private int getLength(ListNode head) {
        int length = 0;
        ListNode ptr = head;
        while (ptr != null) {
            length++;
            ptr = ptr.next;
        }
        return length;
    }
}

/*
    给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。*/

 /*   给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。*/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

 class ListNode {
     int val;
    ListNode next;
    ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
 class Solution3 {

/*     if(head == null) return null;
if(head.next == null) return head:
//cur从第二个节点开始ListNode cur = head.next;
//第一个节点next 置为空
     head.next = null:
             while(cur != null) {
//记录下来 当前需要翻转的节点的下一个节点
         ListNode curNext = cur.next;
         cur,next = head;
         head = cur;
         cur = curNext;
         return head;*/
     public ListNode reverseList(ListNode head) {
         ListNode prev = null;
         ListNode curr = head;

         while (curr != null) {
             ListNode nextTemp = curr.next; // 暂存当前节点的下一个节点
             curr.next = prev; // 当前节点的指针指向前一个节点
             prev = curr; // prev 指针向后移动
             curr = nextTemp; // curr 指针向后移动
         }

         return prev; // prev 最终指向反转后的头节点
     }
     public ListNode reverseList2(ListNode head) {
         // 递归终止条件：如果链表为空或只有一个节点，则直接返回该节点
         if (head == null || head.next == null) {
             return head;
         }

         ListNode newHead = reverseList(head.next); // 递归反转后续链表
         head.next.next = head; // 将当前节点的下一个节点的指针指向当前节点，实现反转
         head.next = null; // 将当前节点的指针指向 null，避免形成环

         return newHead; // 返回反转后的头节点
     }

      /*给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。*/

     public ListNode middleNode(ListNode head) {
         ListNode slow = head;
         ListNode fast = head;

         while (fast != null && fast.next != null) {
             slow = slow.next;
             fast = fast.next.next;
         }

         return slow;
     }

     /*输入一个链表，输出该链表中倒数第k个结点。*/
     /*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
     public class Solution2 {
         public ListNode FindKthToTail(ListNode head, int k) {
             if (head == null || k <= 0) {
                 return null;
             }

             ListNode fast = head;
             ListNode slow = head;

             // 将 fast 指针向前移动 k-1 步
             for (int i = 0; i < k - 1; i++) {
                 if (fast.next != null) {
                     fast = fast.next;
                 } else {
                     // 如果链表长度小于 k，返回 null
                     return null;
                 }
             }

             // 同时移动 fast 和 slow 指针
             while (fast.next != null) {
                 fast = fast.next;
                 slow = slow.next;
             }

             return slow;
         }
     }

     /*将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 */

     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
         ListNode dummy = new ListNode(0); // 创建虚拟头节点
         ListNode curr = dummy; // 当前节点指针

         while (list1 != null && list2 != null) {
             if (list1.val <= list2.val) {
                 curr.next = list1;
                 list1 = list1.next;
             } else {
                 curr.next = list2;
                 list2 = list2.next;
             }
             curr = curr.next;
         }

         // 将剩余的链表部分直接接到 curr 的后面
         if (list1 != null) {
             curr.next = list1;
         }
         if (list2 != null) {
             curr.next = list2;
         }

         return dummy.next; // 返回合并后的链表头节点
     }
     /*现有一链表的头指针 ListNode* pHead，给一定值x，
     编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。*/
     public class Partition {
         public ListNode partition(ListNode pHead, int x) {
             ListNode smallerHead = new ListNode(0); // 用于存储小于 x 的节点的链表
             ListNode greaterHead = new ListNode(0); // 用于存储大于等于 x 的节点的链表
             ListNode smallerTail = smallerHead; // smallerTail 指向 smallerHead 的尾节点
             ListNode greaterTail = greaterHead; // greaterTail 指向 greaterHead 的尾节点

             while (pHead != null) {
                 if (pHead.val < x) {
                     smallerTail.next = pHead;
                     smallerTail = smallerTail.next;
                 } else {
                     greaterTail.next = pHead;
                     greaterTail = greaterTail.next;
                 }
                 pHead = pHead.next;
             }

             // 将两个链表连接起来
             smallerTail.next = greaterHead.next;
             greaterTail.next = null; // 确保最后一个节点的 next 为 null

             return smallerHead.next; // 返回新链表的头指针
         }
     }


     /*对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
     给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

     比如：1->2->2->1*/

         public boolean chkPalindrome(ListNode A) {
             if (A == null || A.next == null) {
                 return true; // 链表为空或只有一个节点时，视为回文结构
             }

             ListNode fast = A; // 快指针
             ListNode slow = A; // 慢指针

             // 使用快慢指针找到链表的中间节点
             while (fast != null && fast.next != null) {
                 fast = fast.next.next;
                 slow = slow.next;
             }

             // 反转链表的后半部分
             ListNode prev = null;
             ListNode curr = slow;
             ListNode next = null;

             while (curr != null) {

                 next = curr.next;
                 curr.next = prev;
                 prev = curr;
                 curr = next;
             }

             // 比较链表的前半部分和反转后的后半部分
             ListNode left = A; // 前半部分的头节点
             ListNode right = prev; // 反转后的后半部分的头节点

             while (left != null && right != null) {
                 if (left.val != right.val) {
                     return false; // 如果节点的值不相等，则链表不是回文结构
                 }
                 left = left.next;
                 right = right.next;
             }

             return true; // 所有节点的值都相等，链表是回文结构
         }
 }

